package com.tencent.mtt.supportui.utils.struct;

import android.util.Log;

import java.util.Map;

/**
 * Created by leonardgong on 2017/12/7 0007.
 */

/**
 * Base implementation of {@link ArrayMap} that doesn't include any standard
 * Java
 * container API interoperability. These features are generally heavier-weight
 * ways
 * to interact with the container, so discouraged, but they can be useful to
 * make it
 * easier to use as a drop-in replacement for HashMap. If you don't need them,
 * this
 * class can be preferrable since it doesn't bring in any of the implementation
 * of those
 * APIs, allowing that code to be stripped by ProGuard.
 */
public class SimpleArrayMap<K, V>
{
	private static final boolean	DEBUG		= false;
	private static final String		TAG			= "ArrayMap";

	/**
	 * The minimum amount by which the capacity of a ArrayMap will increase.
	 * This is tuned to be relatively space-efficient.
	 */
	private static final int		BASE_SIZE	= 4;

	/**
	 * Maximum number of entries to have in array caches.
	 */
	private static final int		CACHE_SIZE	= 10;

	/**
	 * Caches of small array objects to avoid spamming garbage. The cache
	 * Object[] variable is a pointer to a linked list of array objects.
	 * The first entry in the array is a pointer to the next array in the
	 * list; the second entry is a pointer to the int[] hash code array for it.
	 */
	static Object[]					mBaseCache;
	static int						mBaseCacheSize;
	static Object[]					mTwiceBaseCache;
	static int						mTwiceBaseCacheSize;

	int[]							mHashes;
	Object[]						mArray;
	int								mSize;

	int indexOf(Object key, int hash)
	{
		final int N = mSize;

		// Important fast case: if nothing is in here, nothing to look for.
		if (N == 0)
		{
			return ~0;
		}

		int index = ContainerHelpers.binarySearch(mHashes, N, hash);

		// If the hash code wasn't found, then we have no entry for this key.
		if (index < 0)
		{
			return index;
		}

		// If the key at the returned index matches, that's what we want.
		if (key.equals(mArray[index << 1]))
		{
			return index;
		}

		// Search for a matching key after the index.
		int end;
		for (end = index + 1; end < N && mHashes[end] == hash; end++)
		{
			if (key.equals(mArray[end << 1]))
				return end;
		}

		// Search for a matching key before the index.
		for (int i = index - 1; i >= 0 && mHashes[i] == hash; i--)
		{
			if (key.equals(mArray[i << 1]))
				return i;
		}

		// Key not found -- return negative value indicating where a
		// new entry for this key should go.  We use the end of the
		// hash chain to reduce the number of array entries that will
		// need to be copied when inserting.
		return ~end;
	}

	int indexOfNull()
	{
		final int N = mSize;

		// Important fast case: if nothing is in here, nothing to look for.
		if (N == 0)
		{
			return ~0;
		}

		int index = ContainerHelpers.binarySearch(mHashes, N, 0);

		// If the hash code wasn't found, then we have no entry for this key.
		if (index < 0)
		{
			return index;
		}

		// If the key at the returned index matches, that's what we want.
		if (null == mArray[index << 1])
		{
			return index;
		}

		// Search for a matching key after the index.
		int end;
		for (end = index + 1; end < N && mHashes[end] == 0; end++)
		{
			if (null == mArray[end << 1])
				return end;
		}

		// Search for a matching key before the index.
		for (int i = index - 1; i >= 0 && mHashes[i] == 0; i--)
		{
			if (null == mArray[i << 1])
				return i;
		}

		// Key not found -- return negative value indicating where a
		// new entry for this key should go.  We use the end of the
		// hash chain to reduce the number of array entries that will
		// need to be copied when inserting.
		return ~end;
	}

	private void allocArrays(final int size)
	{
		if (size == (BASE_SIZE * 2))
		{
			synchronized (ArrayMap.class)
			{
				if (mTwiceBaseCache != null)
				{
					final Object[] array = mTwiceBaseCache;
					mArray = array;
					mTwiceBaseCache = (Object[]) array[0];
					mHashes = (int[]) array[1];
					array[0] = array[1] = null;
					mTwiceBaseCacheSize--;
					if (DEBUG)
						Log.d(TAG, "Retrieving 2x cache " + mHashes + " now have " + mTwiceBaseCacheSize + " entries");
					return;
				}
			}
		}
		else if (size == BASE_SIZE)
		{
			synchronized (ArrayMap.class)
			{
				if (mBaseCache != null)
				{
					final Object[] array = mBaseCache;
					mArray = array;
					mBaseCache = (Object[]) array[0];
					mHashes = (int[]) array[1];
					array[0] = array[1] = null;
					mBaseCacheSize--;
					if (DEBUG)
						Log.d(TAG, "Retrieving 1x cache " + mHashes + " now have " + mBaseCacheSize + " entries");
					return;
				}
			}
		}

		mHashes = new int[size];
		mArray = new Object[size << 1];
	}

	private static void freeArrays(final int[] hashes, final Object[] array, final int size)
	{
		if (hashes.length == (BASE_SIZE * 2))
		{
			synchronized (ArrayMap.class)
			{
				if (mTwiceBaseCacheSize < CACHE_SIZE)
				{
					array[0] = mTwiceBaseCache;
					array[1] = hashes;
					for (int i = (size << 1) - 1; i >= 2; i--)
					{
						array[i] = null;
					}
					mTwiceBaseCache = array;
					mTwiceBaseCacheSize++;
					if (DEBUG)
						Log.d(TAG, "Storing 2x cache " + array + " now have " + mTwiceBaseCacheSize + " entries");
				}
			}
		}
		else if (hashes.length == BASE_SIZE)
		{
			synchronized (ArrayMap.class)
			{
				if (mBaseCacheSize < CACHE_SIZE)
				{
					array[0] = mBaseCache;
					array[1] = hashes;
					for (int i = (size << 1) - 1; i >= 2; i--)
					{
						array[i] = null;
					}
					mBaseCache = array;
					mBaseCacheSize++;
					if (DEBUG)
						Log.d(TAG, "Storing 1x cache " + array + " now have " + mBaseCacheSize + " entries");
				}
			}
		}
	}

	/**
	 * Create a new empty ArrayMap. The default capacity of an array map is 0, and
	 * will grow once items are added to it.
	 */
	public SimpleArrayMap()
	{
		mHashes = ContainerHelpers.EMPTY_INTS;
		mArray = ContainerHelpers.EMPTY_OBJECTS;
		mSize = 0;
	}

	/**
	 * Create a new ArrayMap with a given initial capacity.
	 */
	public SimpleArrayMap(int capacity)
	{
		if (capacity == 0)
		{
			mHashes = ContainerHelpers.EMPTY_INTS;
			mArray = ContainerHelpers.EMPTY_OBJECTS;
		}
		else
		{
			allocArrays(capacity);
		}
		mSize = 0;
	}

	/**
	 * Create a new ArrayMap with the mappings from the given ArrayMap.
	 */
	public SimpleArrayMap(SimpleArrayMap map)
	{
		this();
		if (map != null)
		{
			putAll(map);
		}
	}

	/**
	 * Make the array map empty. All storage is released.
	 */
	public void clear()
	{
		if (mSize != 0)
		{
			freeArrays(mHashes, mArray, mSize);
			mHashes = ContainerHelpers.EMPTY_INTS;
			mArray = ContainerHelpers.EMPTY_OBJECTS;
			mSize = 0;
		}
	}

	/**
	 * Ensure the array map can hold at least <var>minimumCapacity</var>
	 * items.
	 */
	public void ensureCapacity(int minimumCapacity)
	{
		if (mHashes.length < minimumCapacity)
		{
			final int[] ohashes = mHashes;
			final Object[] oarray = mArray;
			allocArrays(minimumCapacity);
			if (mSize > 0)
			{
				System.arraycopy(ohashes, 0, mHashes, 0, mSize);
				System.arraycopy(oarray, 0, mArray, 0, mSize << 1);
			}
			freeArrays(ohashes, oarray, mSize);
		}
	}

	/**
	 * Check whether a key exists in the array.
	 *
	 * @param key The key to search for.
	 * @return Returns true if the key exists, else false.
	 */
	public boolean containsKey(Object key)
	{
		return key == null ? (indexOfNull() >= 0) : (indexOf(key, key.hashCode()) >= 0);
	}

	int indexOfValue(Object value)
	{
		final int N = mSize * 2;
		final Object[] array = mArray;
		if (value == null)
		{
			for (int i = 1; i < N; i += 2)
			{
				if (array[i] == null)
				{
					return i >> 1;
				}
			}
		}
		else
		{
			for (int i = 1; i < N; i += 2)
			{
				if (value.equals(array[i]))
				{
					return i >> 1;
				}
			}
		}
		return -1;
	}

	/**
	 * Check whether a value exists in the array. This requires a linear search
	 * through the entire array.
	 *
	 * @param value The value to search for.
	 * @return Returns true if the value exists, else false.
	 */
	public boolean containsValue(Object value)
	{
		return indexOfValue(value) >= 0;
	}

	/**
	 * Retrieve a value from the array.
	 * 
	 * @param key The key of the value to retrieve.
	 * @return Returns the value associated with the given key,
	 *         or null if there is no such key.
	 */
	public V get(Object key)
	{
		final int index = key == null ? indexOfNull() : indexOf(key, key.hashCode());
		return index >= 0 ? (V) mArray[(index << 1) + 1] : null;
	}

	/**
	 * Return the key at the given index in the array.
	 * 
	 * @param index The desired index, must be between 0 and {@link #size()}-1.
	 * @return Returns the key stored at the given index.
	 */
	public K keyAt(int index)
	{
		return (K) mArray[index << 1];
	}

	/**
	 * Return the value at the given index in the array.
	 * 
	 * @param index The desired index, must be between 0 and {@link #size()}-1.
	 * @return Returns the value stored at the given index.
	 */
	public V valueAt(int index)
	{
		return (V) mArray[(index << 1) + 1];
	}

	/**
	 * Set the value at a given index in the array.
	 * 
	 * @param index The desired index, must be between 0 and {@link #size()}-1.
	 * @param value The new value to store at this index.
	 * @return Returns the previous value at the given index.
	 */
	public V setValueAt(int index, V value)
	{
		index = (index << 1) + 1;
		V old = (V) mArray[index];
		mArray[index] = value;
		return old;
	}

	/**
	 * Return true if the array map contains no items.
	 */
	public boolean isEmpty()
	{
		return mSize <= 0;
	}

	/**
	 * Add a new value to the array map.
	 * 
	 * @param key The key under which to store the value. <b>Must not be null.</b>
	 *            If
	 *            this key already exists in the array, its value will be replaced.
	 * @param value The value to store for the given key.
	 * @return Returns the old value that was stored for the given key, or null if
	 *         there
	 *         was no such key.
	 */
	public V put(K key, V value)
	{
		final int hash;
		int index;
		if (key == null)
		{
			hash = 0;
			index = indexOfNull();
		}
		else
		{
			hash = key.hashCode();
			index = indexOf(key, hash);
		}
		if (index >= 0)
		{
			index = (index << 1) + 1;
			final V old = (V) mArray[index];
			mArray[index] = value;
			return old;
		}

		index = ~index;
		if (mSize >= mHashes.length)
		{
			final int n = mSize >= (BASE_SIZE * 2) ? (mSize + (mSize >> 1)) : (mSize >= BASE_SIZE ? (BASE_SIZE * 2) : BASE_SIZE);

			if (DEBUG)
				Log.d(TAG, "put: grow from " + mHashes.length + " to " + n);

			final int[] ohashes = mHashes;
			final Object[] oarray = mArray;
			allocArrays(n);

			if (mHashes.length > 0)
			{
				if (DEBUG)
					Log.d(TAG, "put: copy 0-" + mSize + " to 0");
				System.arraycopy(ohashes, 0, mHashes, 0, ohashes.length);
				System.arraycopy(oarray, 0, mArray, 0, oarray.length);
			}

			freeArrays(ohashes, oarray, mSize);
		}

		if (index < mSize)
		{
			if (DEBUG)
				Log.d(TAG, "put: move " + index + "-" + (mSize - index) + " to " + (index + 1));
			System.arraycopy(mHashes, index, mHashes, index + 1, mSize - index);
			System.arraycopy(mArray, index << 1, mArray, (index + 1) << 1, (mSize - index) << 1);
		}

		mHashes[index] = hash;
		mArray[index << 1] = key;
		mArray[(index << 1) + 1] = value;
		mSize++;
		return null;
	}

	/**
	 * Perform a {@link #put(Object, Object)} of all key/value pairs in
	 * <var>array</var>
	 * 
	 * @param array The array whose contents are to be retrieved.
	 */
	public void putAll(SimpleArrayMap<? extends K, ? extends V> array)
	{
		final int N = array.mSize;
		ensureCapacity(mSize + N);
		if (mSize == 0)
		{
			if (N > 0)
			{
				System.arraycopy(array.mHashes, 0, mHashes, 0, N);
				System.arraycopy(array.mArray, 0, mArray, 0, N << 1);
				mSize = N;
			}
		}
		else
		{
			for (int i = 0; i < N; i++)
			{
				put(array.keyAt(i), array.valueAt(i));
			}
		}
	}

	/**
	 * Remove an existing key from the array map.
	 * 
	 * @param key The key of the mapping to remove.
	 * @return Returns the value that was stored under the key, or null if there
	 *         was no such key.
	 */
	public V remove(Object key)
	{
		int index = key == null ? indexOfNull() : indexOf(key, key.hashCode());
		if (index >= 0)
		{
			return removeAt(index);
		}

		return null;
	}

	/**
	 * Remove the key/value mapping at the given index.
	 * 
	 * @param index The desired index, must be between 0 and {@link #size()}-1.
	 * @return Returns the value that was stored at this index.
	 */
	public V removeAt(int index)
	{
		final Object old = mArray[(index << 1) + 1];
		if (mSize <= 1)
		{
			// Now empty.
			if (DEBUG)
				Log.d(TAG, "remove: shrink from " + mHashes.length + " to 0");
			freeArrays(mHashes, mArray, mSize);
			mHashes = ContainerHelpers.EMPTY_INTS;
			mArray = ContainerHelpers.EMPTY_OBJECTS;
			mSize = 0;
		}
		else
		{
			if (mHashes.length > (BASE_SIZE * 2) && mSize < mHashes.length / 3)
			{
				// Shrunk enough to reduce size of arrays.  We don't allow it to
				// shrink smaller than (BASE_SIZE*2) to avoid flapping between
				// that and BASE_SIZE.
				final int n = mSize > (BASE_SIZE * 2) ? (mSize + (mSize >> 1)) : (BASE_SIZE * 2);

				if (DEBUG)
					Log.d(TAG, "remove: shrink from " + mHashes.length + " to " + n);

				final int[] ohashes = mHashes;
				final Object[] oarray = mArray;
				allocArrays(n);

				mSize--;
				if (index > 0)
				{
					if (DEBUG)
						Log.d(TAG, "remove: copy from 0-" + index + " to 0");
					System.arraycopy(ohashes, 0, mHashes, 0, index);
					System.arraycopy(oarray, 0, mArray, 0, index << 1);
				}
				if (index < mSize)
				{
					if (DEBUG)
						Log.d(TAG, "remove: copy from " + (index + 1) + "-" + mSize + " to " + index);
					System.arraycopy(ohashes, index + 1, mHashes, index, mSize - index);
					System.arraycopy(oarray, (index + 1) << 1, mArray, index << 1, (mSize - index) << 1);
				}
			}
			else
			{
				mSize--;
				if (index < mSize)
				{
					if (DEBUG)
						Log.d(TAG, "remove: move " + (index + 1) + "-" + mSize + " to " + index);
					System.arraycopy(mHashes, index + 1, mHashes, index, mSize - index);
					System.arraycopy(mArray, (index + 1) << 1, mArray, index << 1, (mSize - index) << 1);
				}
				mArray[mSize << 1] = null;
				mArray[(mSize << 1) + 1] = null;
			}
		}
		return (V) old;
	}

	/**
	 * Return the number of items in this array map.
	 */
	public int size()
	{
		return mSize;
	}

	/**
	 * {@inheritDoc}
	 *
	 * <p>
	 * This implementation returns false if the object is not a map, or
	 * if the maps have different sizes. Otherwise, for each key in this map,
	 * values of both maps are compared. If the values for any key are not
	 * equal, the method returns false, otherwise it returns true.
	 */
	@Override
	public boolean equals(Object object)
	{
		if (this == object)
		{
			return true;
		}
		if (object instanceof Map)
		{
			Map<?, ?> map = (Map<?, ?>) object;
			if (size() != map.size())
			{
				return false;
			}

			try
			{
				for (int i = 0; i < mSize; i++)
				{
					K key = keyAt(i);
					V mine = valueAt(i);
					Object theirs = map.get(key);
					if (mine == null)
					{
						if (theirs != null || !map.containsKey(key))
						{
							return false;
						}
					}
					else if (!mine.equals(theirs))
					{
						return false;
					}
				}
			}
			catch (NullPointerException ignored)
			{
				return false;
			}
			catch (ClassCastException ignored)
			{
				return false;
			}
			return true;
		}
		return false;
	}

	/**
	 * {@inheritDoc}
	 */
	@Override
	public int hashCode()
	{
		final int[] hashes = mHashes;
		final Object[] array = mArray;
		int result = 0;
		for (int i = 0, v = 1, s = mSize; i < s; i++, v += 2)
		{
			Object value = array[v];
			result += hashes[i] ^ (value == null ? 0 : value.hashCode());
		}
		return result;
	}

	/**
	 * {@inheritDoc}
	 *
	 * <p>
	 * This implementation composes a string by iterating over its mappings. If
	 * this map contains itself as a key or a value, the string "(this Map)"
	 * will appear in its place.
	 */
	@Override
	public String toString()
	{
		if (isEmpty())
		{
			return "{}";
		}

		StringBuilder buffer = new StringBuilder(mSize * 28);
		buffer.append('{');
		for (int i = 0; i < mSize; i++)
		{
			if (i > 0)
			{
				buffer.append(", ");
			}
			Object key = keyAt(i);
			if (key != this)
			{
				buffer.append(key);
			}
			else
			{
				buffer.append("(this Map)");
			}
			buffer.append('=');
			Object value = valueAt(i);
			if (value != this)
			{
				buffer.append(value);
			}
			else
			{
				buffer.append("(this Map)");
			}
		}
		buffer.append('}');
		return buffer.toString();
	}
}
